/*
 * Copyright (c) 2018-2022, 四川蜀天梦图数据科技有限公司.
 * All rights reserved.
 */

package link_list

// https://leetcode.cn/problems/reverse-linked-list-ii/ leetcode-92
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if left == right {
		return head
	}

	var leftNode, leftPrev, rightNode, rightNext *ListNode
	index := 1
	for node := head; node != nil; node = node.Next {
		if index == left {
			leftNode = node
		}

		if index == left-1 {
			leftPrev = node
		}

		if index == right {
			rightNode = node
		}

		if index == right+1 {
			rightNext = node
			break
		}
		index++
	}
	index = left

	var newHead *ListNode
	curNode := leftNode
	for index <= right {
		tmp := curNode.Next
		curNode.Next = newHead
		newHead = curNode
		curNode = tmp
		index++
	}

	if leftPrev != nil {
		leftPrev.Next = rightNode
	} else {
		head = newHead
	}
	leftNode.Next = rightNext

	return head
}

func reverseBetween1(head *ListNode, left int, right int) *ListNode {
	if left == right {
		return head
	}

	var leftPerv, leftNode, headNode *ListNode

	index := 1
	for node := head; node != nil; {
		next := node.Next

		if index == left-1 {
			leftPerv = node
		}

		if index == left {
			leftNode = node
			headNode = node
		}

		if index > left && index <= right {
			leftNode.Next = next
			node.Next = headNode
			headNode = node
		}

		if index > right {
			break
		}

		index++
		node = next
	}

	if leftPerv != nil {
		leftPerv.Next = headNode
	} else {
		head = headNode
	}

	return head
}
